package com.leetcode.根据算法进行分类.动态规划算法相关;

/**
 * @author: ZhouBert
 * @date: 2021/2/20
 * @description: 795. 区间子数组个数
 * https://leetcode-cn.com/problems/number-of-subarrays-with-bounded-maximum/
 */
public class B_795_区间子数组个数 {

	public static void main(String[] args) {
		B_795_区间子数组个数 action = new B_795_区间子数组个数();
		test1(action);
		test2(action);
	}

	public static void test1(B_795_区间子数组个数 action) {
		// 3
		int[] A = new int[]{2, 1, 4, 3};
		int L = 2;
		int R = 3;
		int res = action.numSubarrayBoundedMax(A, L, R);
		System.out.println("res = " + res);
	}

	public static void test2(B_795_区间子数组个数 action) {
		// 22
		int[] A = new int[]{73, 55, 36, 5, 55, 14, 9, 7, 72, 52};
		int L = 32;
		int R = 69;
		int res = action.numSubarrayBoundedMax(A, L, R);
		System.out.println("res = " + res);
	}

	/**
	 * 这种求连续子数组的问题，可以考虑用 dp ，滑动窗口等来解决。
	 * 但是 最大值的问题 得想个办法解决？？？？
	 *
	 * @param A
	 * @param L [
	 * @param R ]
	 * @return
	 */
	public int numSubarrayBoundedMaxFail(int[] A, int L, int R) {
		int len = A.length;
		int[] dp = new int[len];
		//前一个元素是否合法
		boolean lastIsLegal = false;
		//处理首个元素
		if (A[0] >= L && A[0] <= R) {
			//索引处的值符合范围要求时
			dp[0] = 1;
			lastIsLegal = true;
		}
		int res = dp[0];
		for (int i = 1; i < len; i++) {
			if (A[i] < A[i - 1]) {
				//如果当前 小于 前一个 -> 说明前一个元素说了算
				if (lastIsLegal) {
					//如果前一个元素合法
					if (A[i] >= L && A[i] <= R) {
						//并且当前元素也合法
						dp[i] = dp[i - 1] + 1;
						//lastIsLegal = true;
					} else {
						//当前元素不合法
						dp[i] = dp[i - 1];
						lastIsLegal = false;
					}
				} else {
					//上一个元素不合法
					if (A[i] >= L && A[i] <= R) {
						//当前元素合法
						dp[i] = 1;
						lastIsLegal = true;
					} else {
						//当前元素不合法
						dp[i] = 0;
						//lastIsLegal = false;
					}
				}
			} else {
				//如果当前 大于等于 前一个
				if (A[i] >= L && A[i] <= R) {
					//索引处的值符合范围要求时 -> 说明可以使用 当前元素
					dp[i] = dp[i - 1] + 1;

					lastIsLegal = true;
				} else {
					dp[i] = 0;
					lastIsLegal = false;
				}
			}

			res += dp[i];
		}

		return res;
	}

	/**
	 * 看了题解，说要先根据 LR 的问题重塑数组，看看有木有新的启发。
	 * 此时问题就变成了：求只包含1 不包含 2 的连续子数组的个数。
	 * --
	 * 但是往这个方向我也想不到 O(n) 的算法；
	 * 看了题解才发现：构造一个 小于等于 x 的子数组的数量
	 * （关键是用 集合相减的思路！）
	 * 然后再根据这个做 dp
	 * --
	 * 在 countArr 中由于只记录上一个值，所以不需要维护一个 dp 数组
	 *
	 * @param A
	 * @param L [
	 * @param R ]
	 * @return
	 */
	public int numSubarrayBoundedMaxByDP(int[] A, int L, int R) {
		return countArrByDP(A, R + 1) - countArrByDP(A, L);
	}

	/**
	 * 求出 A 中小于等于 v 的子数组个数
	 * --
	 * 细节优化一下，改为 小于
	 *
	 * @param A
	 * @param v
	 * @return
	 */
	private int countArrByDP(int[] A, int v) {
		int len = A.length;
		int[] dp = new int[len];
		dp[0] = A[0] < v ? 1 : 0;
		int res = dp[0];
		for (int i = 1; i < len; i++) {
			if (A[i] < v) {
				dp[i] = dp[i - 1] + 1;
			} else {
				dp[i] = 0;
			}
			res += dp[i];
		}

		return res;
	}

	/**
	 * 在 countArr 中由于只记录上一个值，所以不需要维护一个 dp 数组
	 * 的优化版本！
	 * @param A
	 * @param L
	 * @param R
	 * @return
	 */
	public int numSubarrayBoundedMax(int[] A, int L, int R) {
		int len = A.length;
		return countArr(A, R + 1, len) - countArr(A, L, len);
	}

	/**
	 * 求出 A 中小于 v 的子数组个数
	 *
	 * @param A
	 * @param value
	 * @param len
	 * @return
	 */
	private int countArr(int[] A, int value, int len) {
		int res = 0, last = 0;
		for (int i = 0; i < len; i++) {
			if (A[i] < value) {
				last++;
				res += last;
			} else {
				last = 0;
			}
		}

		return res;
	}


}
